#define _CRT_SECURE_NO_WARNINGS
//dfs
class Solution {
public:
    vector<int> ans;
    vector<int> inorderTraversal(TreeNode* root) {
        dfs(root);
        return ans;
    }
    void dfs(TreeNode* root) {
        if (root == nullptr) return;

        if (root->left) dfs(root->left);
        ans.push_back(root->val);
        if (root->right) dfs(root->right);
    }
};
//bfs
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        if (root == nullptr) return ans;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != nullptr || !st.empty()) {
            while (cur != nullptr) {
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* node = st.top();
            st.pop();
            ans.push_back(node->val);
            if (node->right) cur = node->right;
        }
        return ans;
    }
};